/**
 *  Copyright (C) 2013  Piotr Szczepa�ski
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
package edu.pw.elka.gtsna.graph_evaluators;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

import edu.pw.elka.gtsna.graph.Graph;

/**
 * @author Piotr Lech Szczepa�ski
 * @author P.Szczepanski@ii.pw.edu.pl 
 *
 */
public class AverageShortestPathsEvaluator extends GraphEvaluator {

    Queue<Integer> queue; 
    Map<Integer, Double> dist;
    Map<Integer,Integer> sigma;
    
	/**
	 * @param graph
	 */
	public AverageShortestPathsEvaluator(Graph graph) {
		super(graph);
        dist = new HashMap<Integer,Double>();
        queue = new LinkedList<Integer>();
        sigma = new HashMap<Integer,Integer>();
	}

   
    protected double getDistance(int node){
    	return dist.get(node);
    }
    

    protected void singleSourceBFS(int source){
	    for (Integer vert: graph.getAllNodes()) {
            dist.put(vert, Double.MAX_VALUE);
            sigma.put(vert, 0);
            queue.clear();
	    }
	    dist.put(source,0.0);
	    sigma.put(source, 1);
	    queue.add(source);
	    
        while (!queue.isEmpty()) {
        	Integer v = queue.poll();
            for(Integer w: graph.getNeigbours(v)){
                if (dist.get(w) == Double.MAX_VALUE ) {
                    dist.put(w, dist.get(v) + 1);
                    queue.offer(w);
                }
                if (dist.get(w) == dist.get(v) + 1) {
                    sigma.put(w, sigma.get(w) + sigma.get(v));
                }
            }
        }
    }


	@Override
	public double evaluate() {
		
		double averageShortestPaths = 0.0;

		for (int v: graph.getAllNodes()){
			singleSourceBFS(v);
			
			// We sum up all distances between v and u
			for (int u: graph.getAllNodes()){
				if (u != v)
					averageShortestPaths+=sigma.get(u);
			}
			
		}

		return (averageShortestPaths)/(graph.getNumOfNodes()*(graph.getNumOfNodes()-1));

	}

}
